package com.jiang.daily.Q2901;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/05/16 14:00
 */
class Solution {
    // public List<String> getWordsInLongestSubsequence(String[] words, int[] groups) {
    //     int n = words.length;
    //     int[] dp = new int[n];
    //     Arrays.fill(dp, 1);
    //     int[] pre = new int[n];
    //     Arrays.fill(pre, -1);
    //     int maxLen = 1, maxIndex = 0;

    //     for (int i = 1; i < n; i++) {
    //         for (int j = 0; j < i; j++) {
    //             if (groups[i] != groups[j] && 1 + dp[j] > dp[i] && hanmingDistance(words[i], words[j])) {
    //                 dp[i] = 1 + dp[j];
    //                 pre[i] = j;
    //             }
    //         }
    //         if (dp[i] > maxLen) {
    //             maxLen = dp[i];
    //             maxIndex = i;
    //         }
    //     }

    //     List<String> res = new ArrayList<>();
    //     while (maxIndex != -1) {
    //         res.add(words[maxIndex]);
    //         maxIndex = pre[maxIndex];
    //     }
    //     Collections.reverse(res);
    //     return res;
    // }

    // private boolean hanmingDistance(String a, String b) {
    //     if (a.length() != b.length()) {
    //         return false;
    //     }
    //     int count = 0;
    //     for (int i = 0; i < a.length(); i++) {
    //         if (a.charAt(i) != b.charAt(i)) {
    //             count++;
    //         }
    //     }
    //     return count == 1;
    // }

    public List<String> getWordsInLongestSubsequence(String[] words, int[] groups) {
        int n = words.length;
        int[] f = new int[n];
        int[] from = new int[n];
        int maxI = n - 1;
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i + 1; j < n; j++) {
                if(f[j] > f[i] && groups[j] != groups[i] && hanmingDistance(words[i], words[j])){
                    f[i] = f[j];
                    from[i] = j;
                }
            }
            f[i]++;
            if(f[i] > f[maxI]) maxI = i;
        }

        int i = maxI;
        int m = f[i];
        List<String> ans = new ArrayList<>();
        for(int k = 0; k < m; k++){
            ans.add(words[i]);
            i = from[i];
        }
        return ans;
    }

    public boolean hanmingDistance(String s, String t) {
        if(s.length() != t.length()) return false;
        boolean diff = false;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) != t.charAt(i)){
                if(diff) return false;
                diff = true;
            }
        }
        return diff;
    }

}
